/*
 * @lc app=leetcode.cn id=838 lang=typescript
 *
 * [838] 推多米诺
 */

// @lc code=start
function pushDominoes(dominoes: string): string {
  const n = dominoes.length;
  // 广度优先搜索队列
  const queue: number[] = [];
  // 骨牌倒下的时间
  const time: number[] = new Array(n).fill(-1);
  // 骨牌受到哪个方向的推力
  const force: string[] = new Array(n).fill('');
  // 初始化
  for (let i = 0; i < n; i++) {
    if (dominoes[i] === '.') continue;
    queue.push(i);
    time[i] = 0;
    force[i] = dominoes[i];
  }

  // 计算答案
  const ans: string[] = new Array(n).fill('.');
  while (queue.length > 0) {
    const i = queue.shift()!;
    // 只有受到一个方向影响的骨牌才能推动
    if (force[i].length === 1) {
      const f = force[i][0];
      ans[i] = f;
      const ni = f === 'L' ? i - 1 : i + 1;
      // 索引是否合法
      if (ni >= 0 && ni < n) {
        const t = time[i];
        // 如果下一个骨牌没被计算过，则受到当前骨牌方向的影响
        // 加入队列，并更新其方向和倒下的时间
        if (time[ni] === -1) {
          queue.push(ni);
          time[ni] = t + 1;
          force[ni] += f;
        } else if (time[ni] === t + 1) {
          // 下一个骨牌到下的时间是否受当前骨牌影响
          // 如果受影响，则更新其方向
          force[ni] += f;
        }
      }
    }
  }

  return ans.join('');
}
// @lc code=end
